/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/longest-increasing-subsequence
   @Language: C++
   @Datetime: 16-02-09 05:57
   */

// Method 1, DP, Time O(n*n), Space O(n), 123ms
class Solution {
public:
	/**
	 * @param nums: An integer array
	 * @return: The length of LIS (longest increasing subsequence)
	 */
	int longestIncreasingSubsequence(vector<int> &nums) {
		// write your code here
		int n=nums.size(), mx=0;
		vector<int> dp(n,1);
		for(int i=0; i<n; ++i){
			for(int j=0; j<i; ++j){
				if(nums[j]<nums[i]) dp[i]=max(dp[i],dp[j]+1);
			}
			mx=max(mx,dp[i]);
		}
		return mx;
	}
};


// Method 2, Binary Search, Time O(nlogn), Space O(n) 
class Solution {
	// Seem like STL lower_bound()
	int bsearch_low(const vector<int> &nums,int len,int x){
		int begin=0, end=len, mid;
		while(begin<end){
			mid = begin+(end-begin)/2;
			if (nums[mid]<x) begin = mid+1;
			else end = mid;
		}
		return begin;
	}

public:
	/**
	 * @param nums: The integer array
	 * @return: The length of LIS (longest increasing subsequence)
	 * Tip:
	 * Using DP to store increasing subsequence, so the DP[len-1] must be
	 * the biggest of DP[0~len).
	 * If current nums[i] <= DP[len-1], recover certain element in DP by nums[i],
	 * The DP also is increasing subsequence.
	 */
	int longestIncreasingSubsequence(vector<int> nums) {
		// write your code here
		vector<int> DP(nums.size(),0);	// store the increasing subsequence
		int len=0;
		for(int i=0; i<nums.size(); ++i){
			if (len==0 || nums[i]>DP[len-1]) DP[len++]=nums[i];
			//else DP[bsearch_low(DP,len,nums[i])] = nums[i];
			else *lower_bound(DP.begin(),DP.begin()+len,nums[i])=nums[i];
		}
		return len;
	}
};
